package dmsxl.dandiaozhan;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * Author: Zhang Dongwei
 * Date: 2023/9/27 13:43
 */
public class ddz5_84 {
    public static void main(String[] args) {
        int[] height = {2, 1, 5, 6, 2, 3};
        System.out.println(largestRectangleArea(height));
    }

//    暴力解法，力扣超时
    public static int largestRectangleArea1(int[] heights) {
        int res = 0;
        for (int i = 0; i < heights.length; i++){
            int left = i;
            int right = i;
            for (; left >= 0; left --){
                if (heights[left] < heights[i]) break;
            }
            for (;right < heights.length; right ++){
                if (heights[right] < heights[i]) break;
            }
            int w = right - left - 1;
            int h = heights[i];
            res = Math.max(res, w * h);
        }
        return res;
    }

//    题解，单调栈
    public static int largestRectangleArea(int[] heights) {
        int res = 0;
        Deque<Integer> stack = new LinkedList<>();
        int[] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        for (int i = 0; i < heights.length; i++){
            newHeights[i + 1] = heights[i];
        }
        heights = newHeights;
        for (int i = 0; i < heights.length; i++){
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]){
                int mid = stack.peek();
                stack.pop();
                int left = stack.peek();
                int right = i;
                int w = right - left - 1;
                int h = heights[mid];
                res = Math.max(res, w * h);
            }
            stack.push(i);
        }
        return res;
    }
}
